1. Field of the Invention
The invention generally relates to content addressable memories and more particularly to an improved content addressable memory that includes comparator features which decrease precharging activities and, therefore, reduce power consumption.
2. Description of the Related Art
The purpose of a content addressable memory (CAM) is to conduct a large number of searches as quickly as possible. Power dissipation is typically high as speed is the primary design goal. A typical CAM uses dynamic logic to precharge a matchline to the default condition (a match), and conditionally discharge this matchline (to the mismatch condition). After the search operation is completed, the result is detected, and the matchline is precharged to the default match condition. The only time the matchline does not consume precharge power is when it is not discharged between searches (e.g., when there is a match).
It is mathematically trivial to prove that a random bit will match half of the time and mismatch half of the time. Matching 100% of the bits, therefore, becomes decreasingly uncommon as the number of bits increases. For example, the chance of a matching word becomes 0.5n (where n is the number of bits in the word searched) and n is typically much greater than 8, typically between 32 and 288. Since the only time the matchline saves power is when it is not discharged between searches, it is desirable to decrease the number of times that it is discharged. With 8 bits, 0.5n is 0.0039. Thus, such a conventional 8-bit word CAM dissipates all precharged power greater than 99.5% of the time, with random data. While it is important to prevent the meaningless waste of power, slowing CAM and other memory components is much less acceptable. Therefore, there is a need to conserve power in CAMs without sacrificing speed.
It is, therefore, an object of the present invention to provide a structure and method for improving a content addressable memory array having a plurality of serially connected memory sub-arrays (which include at least one memory cell), a matchline connected to each of the sub-arrays, a valid memory cell, a comparator which receives input from the matchline and valid memory cell, a sinkline output from the comparator, and a precharge device. The sinkline and matchline are reset from a first voltage to a second voltage depending upon the results of a compare operation of the input data to the data in the storage device. When the second voltage appears on the matchline and the first voltage appears on the sinkline this indicates a match between the data within all of the sub-arrays and the input data. If the second voltage appears on the sinkline this indicates a mismatch between data within any of the sub-arrays and the input data, or an invalid status within the valid memory cell and maintains the sinkline at the second voltage. If the first of the sub-arrays has data different than the input data, this maintains the sinkline at the second voltage. Further, the matchline is maintained at the second voltage while the sinkline is at the second voltage.
Within each of the sub-arrays, the memory cells are connected serially and include a dynamic transistor for communicating with adjacent memory cells. The invention may also include sense amplifiers, each connected to a different sub-array, wherein the sense amplifiers include a single inverter. Further, if the first of the sub-arrays has data matching the input data, this drops the sinkline to the first voltage. In addition, if the sinkline is at the first voltage and a second of the sub-arrays has data different than the input data, the sinkline is connected to the matchline and drops the matchline to the first voltage. In the alternative condition, if the sinkline is at the first voltage and a second of the sub-arrays has data matching, then the matchline maintains the second voltage.
Therefore, the invention indicates a non-matching memory cell array without discharging the matchline. Instead, the high voltage on the sinkline indicates a non-matching condition. As discussed in greater detail below, only a limited number of circumstances allow the matchline to discharge when indicating a non-match condition. Therefore, by reducing the instances when the matchline will discharge, the invention eliminates the need to precharge the matchline as often and therefore consumes less power than conventional content addressable memory devices that precharge the match line more than 99% of the time.
The invention reduces the number of times the matchline must be precharged by reducing the situations in which the matchline may discharge. Matchline power consumption goes up as the number of bits in a word increase. Match bitline power consumption goes up as the number of words in the array goes up. Therefore, the invention can produce even greater power savings as the sizes of the arrays and sizes of the words increase. Power is also saved by only comparing data words that have been marked as xe2x80x9cvalidxe2x80x9d within the scope of the application. In the event that a word is marked invalid, only the first two sub-arrays compare, leaving the presumably largest subset of the data to save power.